/*
 * @lc app=leetcode.cn id=127 lang=cpp
 * @lcpr version=30204
 *
 * [127] 单词接龙
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) {
            return 0; // 如果 endWord 不在 wordList 中，直接返回 0
        }

        queue<pair<string, int>> q; // 队列存储当前单词和转换步数
        q.push({beginWord, 1});

        while (!q.empty()) {
            auto [currentWord, steps] = q.front();
            q.pop();

            // 遍历当前单词的每一位，尝试替换成其他字母
            for (int i = 0; i < currentWord.size(); ++i) {
                string tempWord = currentWord;
                for (char c = 'a'; c <= 'z'; ++c) {
                    tempWord[i] = c;
                    if (tempWord == currentWord) continue; // 跳过自身

                    if (tempWord == endWord) {
                        return steps + 1; // 找到目标单词，返回步数
                    }

                    if (wordSet.find(tempWord) != wordSet.end()) {
                        q.push({tempWord, steps + 1});
                        wordSet.erase(tempWord); // 防止重复访问
                    }
                }
            }
        }

        return 0; // 无法转换到 endWord
    }
};
// @lc code=end



/*
// @lcpr case=start
// "hit"\n"cog"\n["hot","dot","dog","lot","log","cog"]\n
// @lcpr case=end

// @lcpr case=start
// "hit"\n"cog"\n["hot","dot","dog","lot","log"]\n
// @lcpr case=end

 */

